package 字典树;

/**
 * 211. 添加与搜索单词 - 数据结构设计
 * 请你设计一个数据结构，支持 添加新单词 和 查找字符串是否与任何先前添加的字符串匹配 。
 * 实现词典类 WordDictionary ：
 * WordDictionary() 初始化词典对象
 * void addWord(word) 将 word 添加到数据结构中，之后可以对它进行匹配
 * bool search(word) 如果数据结构中存在字符串与 word 匹配，则返回 true ；否则，返回  false 。word 中可能包含一些 '.' ，每个 . 都可以表示任何一个字母。
 *
 * 1:问题分析：
     * 题目要求设计一个支持以下两种操作的数据结构：
     * 添加单词：将单词存入数据结构。
     * 搜索单词：检查数据结构中是否存在该单词。搜索时支持通配符 .，表示可以匹配任意字符。
 * 关键点：
 *   * 需要高效处理通配符 . 的模糊匹配。
 *   * 前缀树（Trie）天然适合处理字符串的插入和前缀匹配，但需要扩展搜索逻辑以支持通配符。
 *  2: 数据结构分析：
 *      1：TrieNode 节点
 *          每个节点包含一个长度为 26 的子节点数组（对应小写字母 a-z）。
 *          一个布尔值 isEnd，表示当前节点是否是某个单词的结尾。
 *      2：WordDictionary 类：
 *          维护一个根节点 root。
 *          提供插入单词和搜索单词的方法，其中搜索需支持通配符 .。
 *  3：核心逻辑：
 *      1： 插入单词
 *          与标准 Trie 的插入逻辑一致：逐字符构建路径，末尾标记 isEnd。
 *      2：搜索单词（含通配符 .）
 *          普通字符：直接检查对应子节点是否存在。
 *          通配符 .：需要遍历当前节点的所有非空子节点，递归检查剩余字符是否匹配。
 *          递归终止条件：当处理到单词末尾时，检查当前节点是否是单词结尾（isEnd）。
 */
public class L_211 {

    private TrieNode root;

    public L_211() {
        root = new TrieNode();
    }

    /// 插入单词（与标准 Trie 逻辑一致）
    public void addWord(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()){
            int index = c - 'a';
            if(node.children[index] == null){
                node.children[index] = new TrieNode();
            }
            node = node.children[index];
        }
        node.isEnd = true;
    }

    // 搜索单词（支持通配符 .）
    public boolean search(String word) {
        return searchInNode(word,0,root);
    }

    // 递归辅助函数：从指定节点开始匹配单词的第 i 个字符
    private boolean searchInNode(String word, int i, TrieNode node){
        if(i == word.length()){ // 递归终止条件：处理到单词末尾
            return node.isEnd;
        }
        char c = word.charAt(i);
        // 普通字符，两种场景：是通配符与不是通配符的情况
        if (c != '.'){
            // 普通字符，直接检测子节点
            int index = c - 'a';
            if (node.children[index] == null){
                return false;
            }
            return searchInNode(word,i+1,node.children[index]);
        }else {
            // 通配符 .：遍历所有非空子节点，递归检查剩余字符
            for (TrieNode child : node.children){
                if (child != null && searchInNode(word,i+1,child)){
                    return true;
                }
            }
        }
        return false;
    }

    // Trie 节点定义
    private static class TrieNode {
        TrieNode[] children;
        boolean isEnd;

        public TrieNode() {
            children = new TrieNode[26];
            isEnd = false;
        }
    }
}
